package com.company.lianbiao;

import com.sun.org.apache.regexp.internal.REUtil;
import javafx.scene.media.VideoTrack;
import org.hamcrest.core.SubstringMatcher;
import org.junit.Test;

import javax.annotation.Resource;
import javax.swing.text.AbstractDocument;
import java.util.*;

/**
 * @description:
 * @author: Code-zyc
 * @date: Created in 2021/12/3 12:16
 * @version: 1.0
 * @modified By:
 */
public class TestLianBiao {

    //      Definition for singly-linked list.
    public class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
//      int count=0;

    @Test
    public void test() {
        Map<Integer,Integer> nodes=new HashMap<>();
        nodes.put(1,1);
        Integer integer = nodes.get(1);
        System.out.println(integer);
        System.out.println(nodes.get(null));
    }

    /**旋转链表
     给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。


     * */
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
            ListNode index=head;  //负责移动的游标
            int length=0;  //记录链表的长度
            while (index.next!=null){  //这一次的循环主要是 得到链表的长度  然后让他的尾巴和头部链接起来
                length++;
                index=index.next;
            }
            length++;//补充最后一次计数
            index.next=head;  //这一个是形成一个环
            //此时利用找到的规律 ：
            // 因为这个链表现在已经是个环了 得出以下的规律：
            //头指针应该是多少：  头指针就是 原来的头指针移动 length-（k%length）的位置
            //那个部分 应该断开就是等于.next=null   原来尾巴的部分移动 length-k（k%length）的位置
            //按照这个规律 可以进行这样的编码
            //首先设置头的位置
        for (int i = 0; i < length - (k % length); i++) {
            head=head.next;
            index=index.next;
        }
        index.next=null;
        return head;


    }



    /**复制带随机指针的链表
     给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

     构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

     作者：力扣 (LeetCode)
     链接：https://leetcode-cn.com/leetbook/read/linked-list/fdi26/
     来源：力扣（LeetCode）
     著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * */

    public Node copyRandomList(Node head) {
        Map<Node,Node> nodes=new HashMap<>();//前面的Node 代表head里面的 node  后面的Node 代表的是新的Node

        Node temple=head;//临时的变量
        while (temple!=null){  //这一遍的  遍历 主要是把所有的node 实列化
            // 至于random  下一次循环在进行操作
            nodes.put(temple,new Node(temple.val));
            temple=temple.next;
        }
        //这一步是  进行random和 next 的操作
        temple=head;
        while (temple!=null){
            //现在根据  head  对应的 来获取 刚刚创建的
            Node node = nodes.get(temple);
            //这一步就是设置好  next的
            node.next=nodes.get(temple.next);
            //这一步就是设置  random的
            node.random=nodes.get(temple.random);
            temple= temple.next;
        }
        return nodes.get(head);
    }



    /**扁平化多级双向链表
     多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

     给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

     作者：力扣 (LeetCode)
     链接：https://leetcode-cn.com/leetbook/read/linked-list/fw8v5/
     来源：力扣（LeetCode）
     著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * */
//    Node result=new Node();
//    Node temple=result;
//    public Node flatten(Node head) {
//        if (head==null){
//            return head;
//        }
//
//        flattenDiGui(head);
//        result.next.prev=null;
//        return  result.next;
//
//
//    }
//    public void flattenDiGui(Node head){
//
//        Node node=new Node();
//        node.val=head.val;
//        node.prev=temple;
//        temple.next=node;
//        temple=node;
//
//        if (head.child!=null){
//            flattenDiGui(head.child);
//        }
//        if (head.next!=null){
//            flattenDiGui(head.next);
//        }
//    }


    /**两数相加
     给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

     请你将两个数相加，并以相同形式返回一个表示和的链表。

     你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

     作者：力扣 (LeetCode)
     链接：https://leetcode-cn.com/leetbook/read/linked-list/fv6w7/
     来源：力扣（LeetCode）
     著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * */
//    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//        ListNode head=new ListNode();
//        ListNode templle=head;
//        while (l1!=null || l2!=null){
//            int val1 =0;
//            int val2 = 0;
//            int sum=0;
//            if (l1!=null){
//                val1= l1.val;
//                l1=l1.next;
//            }
//            if (l2!=null){
//               val2= l2.val;
//               l2=l2.next;
//            }
//            sum=val1+val2+count;
//            count=0;
//            if (sum>=10){
//                count++;
//                sum=sum%10;
//            }
//
//            templle.next=new ListNode(sum);
//            templle=templle.next;
//
//        }
//        if (count!=0){
//            templle.next=new ListNode(count);
//            templle=templle.next;
//        }
//        if (templle.val==0){
//            templle=null;
//        }
//        return head.next;
//    }


    /**
     * 合并两个有序链表
     * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     */

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode head = new ListNode(0); // 随便设置的头
        ListNode temple = head;  //临时的用来指向  尾巴的 方便添加元素
        while (true) {
            int val1 = list1.val;  //从1中取出元素
            int val2 = list2.val;  //从2中取出元素
            if (val1 > val2) {    //进行比较 小的加到 末尾
                temple.next = list2;
                temple = list2;
                list2 = list2.next;
            } else {
                temple.next = list1;
                temple = list1;
                list1 = list1.next;
            }
            //如果有一个为空了 那就  把剩下的全家到 result的末尾即可
            if (list1 == null) {
               temple.next=list2;
                return head.next;
            }

            if (list2 == null) {
                temple.next=list1;
                return head.next;
            }


        }
    }

    /**
     * 回文链表
     * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
     */
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode daoxu = null;
        ListNode slow = head;
        ListNode faste = head.next.next;
        ListNode temple;
        while (true) {
            temple = slow.next;
            slow.next = daoxu;
            daoxu = slow;
            slow = temple;

            if (faste == null) { //代表偶数
                break;
            }

            if (faste.next == null) { //代表奇数  中间那个不用比较
                slow = slow.next;
                break;
            }

            faste = faste.next.next;

        }

        while (slow != null) {
            if (slow.val != daoxu.val) {
                return false;
            }
            slow = slow.next;
            daoxu = daoxu.next;
        }
        return true;
    }

    /**
     * 奇偶链表
     * 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
     * <p>
     * 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
     */

    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode jishuhead = head.next;
        ListNode index = head.next;//游走游标也算是 奇数的尾巴
        ListNode oushu = head;//指向偶数尾巴的
        while (index != null && index.next != null) {
            oushu.next = index.next;//把偶数接上去
            oushu = oushu.next;  //游标更新 偶数的尾巴
            index.next = oushu.next; //更新奇数的尾巴
            index = index.next;
        }
        oushu.next = jishuhead;
        return head;
    }

    /**
     * 除链表元素
     * 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
     */

    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        ListNode slow = head; //慢指针
        ListNode faste = head.next;//快一点的
        while (faste != null) {
            if (faste.val == val) {
                faste = faste.next;
                slow.next = faste;
            } else {
                slow = slow.next;
                faste = faste.next;
            }
        }
        //执行完这个  我们会漏掉一个  第一个节点没有所以在这判断一下
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }


    /**
     * 反转链表
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     */

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {  //判断一下  如果只有一个 那就没必要进行反转了
            return head;
        }
        ListNode slow = head; //慢游标
        ListNode fast = head.next; //快游标
        ListNode temple; //临时得游标
        while (fast != null) {  //建议画图  不太好描述
            temple = fast;
            fast = fast.next;
            temple.next = head;
            head = temple;
            slow.next = fast;
        }
        return head;

    }

    /**
     * 删除链表的倒数第N个节点
     * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     */

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode slow = head;  //一个慢指针
        ListNode faste = head;  //一个快指针
        ListNode temple;   //历时得
        int i = 0;
        while (faste != null && i < n) {  //这一步是设置 快慢指针之间得间距
            i++;
            temple = faste;
            faste = temple.next;
        }
        if (faste == null) {  //如果 间距设置完 faste等于null  那就只有一种情况  就是 第一个节点会被删除
            return head = head.next;
        }
        while (faste.next != null) {  //快慢保持间距移动
            faste = faste.next;
            slow = slow.next;
        }
        slow.next = slow.next.next; //删除对于得节点
        return head;
    }

    /**
     * 相交链表
     * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
     * <p>
     * 图示两个链表在节点 c1 开始相交：
     * <p>
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/linked-list/jjbj2/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> listNodes = new HashSet<>();

        while (headA != null || headB != null) {
            if (headA != null) {
                if (!listNodes.add(headA)) {
                    return headA;
                }
                headA = headA.next;
            }
            if (headB != null) {
                if (!listNodes.add(headB)) {
                    return headB;
                }

                headB = headB.next;
            }

        }
        return null;
    }


    /**
     * 环形链表 II
     * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     * <p>
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
     * <p>
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/linked-list/jjhf6/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

    public ListNode detectCycle(ListNode head) {
        Set<ListNode> listNodes = new HashSet<>();
        while (head != null) {
            if (!listNodes.add(head)) {
                return head;
            }
            head = head.next;
        }
        return null;
    }

    /**
     * 环形链表
     * 给你一个链表的头节点 head ，判断链表中是否有环。
     * <p>
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
     * <p>
     * 如果链表中存在环，则返回 true 。 否则，返回 false 。
     * <p>
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/linked-list/jbex5/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public boolean hasCycle(ListNode head) {
        Set<ListNode> listNodes = new HashSet<>();
        while (head != null) {
            if (!listNodes.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }
}
